The present invention relates to the field of programmable devices, and the systems and methods for programming the same. Programmable devices, such as FPGAs, typically includes thousands of programmable logic cells that use combinations of logic gates and/or look-up tables to perform a logic operation. Programmable devices also include a number of functional blocks having specialized logic devices adapted to specific logic operations, such as adders, multiply and accumulate circuits, phase-locked loops, and memory. The logic cells and functional blocks are interconnected with a configurable switching circuit. The configurable switching circuit selectively routes connections between the logic cells and functional blocks. By configuring the combination of logic cells, functional blocks, and the switching circuit, a programmable device can be adapted to perform virtually any type of information processing function.
A typical compilation process for determining the configuration of a programmable device, referred to compilation, starts with an extraction phase, followed by a logic synthesis phase, a fitting phase, and an assembly phase. The extraction phase takes a user design, typically expressed as a netlist in a hardware description language such as Verilog or VHDL, and produces a set of logic gates implementing the user design. In the logic synthesis phase, the set of logic gates is permuted over the hardware architecture of the programmable device in order to match elements of the user design with corresponding portions of the programmable device. The fitting phase assigns the various portions of the user design to specific logic cells and functional blocks (sometimes referred to as placement) and determines the configuration of the configurable switching circuit used to route signals between these logic cells and functional blocks (sometimes referred to as routing), taking care to satisfy the user timing constraints as much as possible. In the assembly phase, a configuration file defining the programmable device configuration implementing the user design is created. The programmable device configuration can then be loaded into a programmable device to implement the user design. Programmable devices can be configured with the configuration during or after manufacturing.
One of the substantial challenges of the logic synthesis phase is efficiently implementing portions of the user design with programmable device resources. Often, the logic synthesis phase strives to implement portions of the user design with as few logic cells as possible. The hardware description of user designs often includes a number of registers or flip-flops connected by numerous logic gates. Functional logic synthesis techniques evaluate the logic gates specified by the user design and determine corresponding abstract Boolean functions. These Boolean functions can then be mathematically manipulated into forms suitable for efficient implementation by the logic cells of the programmable device.
Boolean functions can be classified as completely specified or incompletely specified. A completely specified function is fully defined for all input values. A completely specified function with N inputs typically requires of look-up table (LUT) of 2N bits to implement. An incompletely specified function is undefined for some input values. The input values corresponding with undefined function values are referred to as don't-care inputs. It is often possible to implement incompletely specified functions with N inputs with a LUT having less than 2N bits. A LUT or logic cell having N inputs but less than 2N bits is referred to as an incomplete LUT. A function that can be implemented using an incomplete LUT is referred to as an incomplete function.
Many user designs specify incomplete functions. For relatively simple functions, these incomplete functions can often be implemented in a single logic cell. For example, if a logic cell includes a pair of five input LUTs connected with a multiplexer controlled by another input, the logic cell only includes enough memory to implement a complete six input function. However, it is often possible to implement a seven input incomplete function with the same logic cell.
For a function having a large number of inputs, it is often necessary to implement the function using a two or more logic cells. To implement functions using multiple logic cells, it is necessary to determine an assignment of function inputs to each logic cell; for each logic cell, an assignment of function inputs and other logic cell outputs to specific logic cell input ports; and to determine the data values to be stored in the one or more LUTs in each logic cell. It is relatively easy to implement complete functions using multiple logic cells. Implementing incomplete functions as complete functions in multiple logic cells is also relatively easy; however, this often uses more programmable device resources than necessary.
There are several prior functional logic synthesis techniques adapted to implement incomplete functions using a minimal amount of programmable device resources. However, these prior techniques perform poorly with incomplete functions having a large number of inputs or being implemented by two or more logic cells. For example, binary decision diagrams (BDD) solver builds a decision tree data structure that enumerate the function outputs for all combinations of input values for different potential sets of logic cell input port assignments. The BDD solver then extracts patterns from this decision tree data structure to determine if a given set of potential logic cell input port assignments can implement the function correctly. Typically, the BDD solver must evaluate decision tree structures for a large number of different potential logic cell input port assignments before finding an acceptable logic cell input port assignment. Additionally, the size of each decision tree structure increases exponentially with the number of inputs. As a result, the BDD solver is very slow and consumes a large amount of memory. Similarly, SAT solvers adapted to find acceptable logic cell input port assignments for incomplete functions are very slow because they must evaluate a large number of potential logic cell input port assignments to find a valid solution.
It is therefore desirable to have a fast and efficient system and method to determine an implementation of incomplete functions using multiple logic cells. It is further desirable for the system and method to quickly screen out potential function implementations that are not likely to provide acceptable results. It is desirable for the system and method to determine look-up table data for one or more look-up tables from a given set of input assignments and to produce logic cells having desired qualities.